package com.jzoffer;

/*
* 统计一个数字在排序数组中出现的次数
* */
public class GetCountOfK {
    public static void main(String[] args) {
        int [] arr = {1,2,3,4,5,5,5,5,6,6,7,8};
        System.out.println(getNumberOfK(arr,5));

    }

    public static int getNumberOfK(int [] array , int k){
        if(array == null || array.length < 1){
            return 0;
        }
        int left = 0;
        int l = 0;
        int right = array.length - 1;
        int r = array.length - 1;

        // 使用二分法 确定左位置
        // 使用二分法 确定右位置
        while (left < right){
            int mid = left + ((right - left) >> 1);
            if(array[mid] < k){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(left > right || array[left] != k){
            return 0;
        }

        // 确定右边界
        while (l < r){
            // 这里后面的mid加1
            int mid = l + ((r - l) >> 1) + 1;
            if(array[mid] > k){
                r = mid - 1;
            }else{
                l = mid;
            }

        }
        if(l > r || array[l] != k || left > r){
            return 0;
        }
        return r - left + 1;
    }
}
